package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
          1
         / \
        2   3
       / \
      4   5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

二叉树上的任一路径上一定有一个结点是所有其他结点的祖先结点，换个表述方法，对于任一结点，以此结点为根的diameter可以表示为 左子树高度+右子树高度+1，而二叉树的diameter就是所有以结点为根的diameter中最大的那个

1.遍历所有节点
2.求以此结点为根的二叉树的diameter
2可以在1进行同时进行

https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode/
*/

func main() {
	tree := GenerateTree([]int{1, 2})
	diameter := diameterOfBinaryTree(tree)
	fmt.Println(diameter)
}

//计算二叉树直径
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
	diameter := 0
	//helper返回某点最大分支路径长度
	var helper func(root *TreeNode) int
	helper = func(root *TreeNode) int {
		if root == nil {
			return -1
		} else if root.Left == nil && root.Right == nil {
			return 0
		}

		left := helper(root.Left) + 1
		right := helper(root.Right) + 1

		diameter = max(diameter, left+right) //left+right以当前节点为转折点的最大路径
		return max(left, right)              //返回以root为根的最大高度
	}

	helper(root)
	return diameter
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
